package codeRandomThoughts.Test235二叉搜索树的最近公共祖先;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return root;
        //找到前往p的路径
        List<TreeNode> pathP = pathToTarget(root, p);
        List<TreeNode> pathQ = pathToTarget(root, q);
        if (pathP.size() > pathQ.size()) {
            List<TreeNode> tem = pathP;
            pathP = pathQ;
            pathQ = tem;
        }
        for (int i = 0; i < pathP.size(); i++) {
            if (pathP.get(i) != pathQ.get(i)) {
                return pathP.get(i - 1);
            }
        }
        return pathP.get(pathP.size() - 1);

    }

    List<TreeNode> pathToTarget(TreeNode root, TreeNode target) {
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        int val = target.val;
        while (root.val != val) {
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
            list.add(root);
        }
        return list;
    }
}
